#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int ans = 0, f = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= c == '-', c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(48 + x % 10);
}
const int N = 1e7 + 5, M = 1e5 + 5;
int cnt, pr[N], vis[N], nxt[N];
set<int> f[2];
inline void prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i])
            pr[++cnt] = i, nxt[i] = i;
        for (int j = 1; j <= cnt && i * pr[j] < N; ++j)
        {
            vis[i * pr[j]] = 1, nxt[i * pr[j]] = nxt[i];
            if (i % pr[j] == 0)
                break;
        }
    }
}
inline void init(int i, int x)
{
    f[i].clear();
    int last = 0;
    while (nxt[x])
    {
        if (last != nxt[x])
            f[i].insert(nxt[x]);
        x /= (last = nxt[x]);
    }
}
signed main()
{
    freopen("never.in", "r", stdin);
    freopen("never.out", "w", stdout);
    prime();
    int T = read();
    while (T--)
    {
        int a = read(), b = read();
        init(0, a), init(1, b);
        auto lcm = [](int a, int b)
        { return a / __gcd(a, b) * b; };
        int ans = min(lcm(a, b), a + b + lcm(*f[0].begin(), 2) + lcm(2, *f[1].begin()));
        for (int i : f[0])
            if (f[1].find(i) != f[1].end())
            {
                ans = min(ans, a + b);
                break;
            }
        vector<int> v1 = {*f[0].begin(), 2}, v2 = {*f[1].begin(), 2};
        for (int i : v1)
            for (int j : v2)
                ans = min(ans, (i != a) * lcm(i, a) + (j != b) * lcm(j, b) + lcm(i, j));
        write(ans), putchar('\n');
    }
    cerr << clock();
    return 0;
}